\documentclass[submission]{FPSAC2017}

\articlenumber{71}
\addbibresource{71_Pfannerer_Rubey_Westbury.bib}

\usepackage{mathtools,amssymb,amscd,url,gensymb}
\usepackage[enableskew]{youngtab}
\usepackage{float}


\usepackage[textsize=footnotesize]{todonotes}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,tikzmark,decorations.markings,fit,calc,shapes}


\newtheorem{thm}{Theorem}[section]
\newtheorem{defn}[thm]{Definition}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lemma}[thm]{Lemma}

\newcommand{\Dfn}[1]{\emph{#1}}
\newcommand{\fS}{\mathfrak{S}}
\newcommand{\fC}{\mathfrak{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\SL}{\mathrm{SL}}
\newcommand{\SO}{\mathrm{SO}}
\newcommand{\Sp}{\mathrm{Sp}}
\newcommand{\GL}{\mathrm{GL}}
\newcommand{\Spin}{\mathrm{Spin}}

\newcommand{\wt}{\mathbf{wt}}
\newcommand{\wgt}{\mu}
\newcommand{\wgtAp}{\pi}
\newcommand{\wgtAn}{\nu}
\newcommand{\osc}{\mathcal{O}} % an oscillating tableau
\newcommand{\alt}{\mathcal{A}} % an alternating tableau
\newcommand{\M}{\mathcal{M}} % the matching corresponding to an
                             % oscillating tableau
\newcommand{\Perm}{\mathcal{P}} % the permutation corresponding to an
                             % alternating tableau
\newcommand{\G}{\mathcal{G}} % a growth diagram

\newcommand{\ltd}{\lessdot} % covering in Young's lattice

\DeclareMathOperator{\rot}{rot} % rotation of a matching
\DeclareMathOperator{\pr}{pr} % promotion of an oscillating tableau
\DeclareMathOperator{\ev}{ev} % evacuation
\DeclareMathOperator{\rev}{rev} % reversal
\DeclareMathOperator{\reco}{rc} % reverse-complement
\DeclareMathOperator{\dom}{dom} % get the dominant weight
\DeclareMathOperator{\cactus}{s} % a generator of the cactus group

%opening
\title{Promotion, Evacuation and Cactus groups}%

\author{Stephan Pfannerer\addressmark{1}\thanks{\href{mailto:Stephan.Pfannerer@tuwien.ac.at}{Stephan.Pfannerer@tuwien.ac.at}}, %
  Martin Rubey\addressmark{1}\thanks{\href{mailto:Martin.Rubey@tuwien.ac.at}{Martin.Rubey@tuwien.ac.at}} \and%
  Bruce W. Westbury\addressmark{2}\thanks{\href{mailto:Bruce.Westbury@warwick.ac.uk}{Bruce.Westbury@warwick.ac.uk}}}
\address{\addressmark{1}Fakult\"at f\"ur Mathematik und
  Geoinformation, TU Wien, Austria\\
  \addressmark{2}Department of Mathematics, University of Warwick,
  Coventry, CV4 7AL}%

\abstract{ The promotion operator on rectangular standard tableaux
  can be generalised to an operator acting on the invariant highest
  weight words in the tensor power of a crystal. For the vector
  representation of a symplectic group the Sundaram correspondence is
  an injective map to perfect matchings. We show that this map
  intertwines promotion and rotation. For the adjoint representation
  of a general linear group we construct a similar map to
  permutations. We show that this map also intertwines promotion and
  rotation. These results are proved using an approach to the action
  of the cactus group using a generalisation of local rules and
  growth diagrams.}%
\keywords{promotion, evacuation, cactus group}

\begin{document}
\maketitle

\section{Introduction}
Our journey begins with the discovery that Sundaram's map from
oscillating tableaux to perfect matchings, regarded as chord diagrams
(as in \cref{fig:chord-diagrams}), intertwines promotion and
rotation, see \cref{thm:rotation-promotion-matchings}.
Oscillating tableaux are highest weight words in a tensor power of
the crystal of the vector representation of the symplectic group
$\Sp(2n)$, and promotion is a natural generalisation of
Sch\"utzenberger's promotion map on standard Young tableaux.

Similarly, there is a natural map from Stembridge's alternating
tableaux, the highest weight words in the $r$-th tensor power of the
crystal for the adjoint representation of the general linear group
$\GL(n)$, to permutations.  It turns out that this map intertwines
promotion and rotation provided that $n\geq r$, see
\cref{thm:rotation-promotion-permutations}.

A convenient setting for these variants of promotion are the cactus
groups, introduced by Devadoss~\cite[def~6.1.2]{MR1718078} and placed
into our context by Henriques and Kamnitzer~\cite{MR2219257}.  These
are infinite groups related to coboundary categories in a similar way
as the braid groups are related to braided categories.  Thus, our
goal is to make the effect of the cactus groups in the coboundary
category of crystals of a complex reductive Lie algebra $\mathfrak g$
transparent.  To do so, we use the local rules discovered by van
Leeuwen~\cite{MR1661263}, generalising the classical local rule for
jeu de taquin by Fomin to all minuscule representations of Lie
groups.  The relation between these local rules and the action of the
cactus groups was established by Lenart~\cite{MR2361854}.

Let $C=C_1\otimes\dots\otimes C_r$ be an $r$-fold tensor product of
crystals.  Then the generators $\cactus_{p,q}$, for
$1\leq p < q\leq r$, of the cactus group map highest weight words of
$C$ bijectively to highest weight words of
$C_1\otimes\dots\otimes C_{p-1}\otimes C_q\otimes\dots\otimes
C_p\otimes C_{q+1}\otimes\dots\otimes C_r$.

For example, when $\mathfrak g$ is the Lie algebra of the special
linear group $\SL(n)$, and $C_1 = \dots = C_r$ is the crystal of its
vector representation, the highest weight words of $C$ are standard
Young tableaux of size $r$ with at most $n$ columns.  Then, the
generator $\cactus_{1,r}$ of the cactus group is precisely
Sch\"utzenberger's evacuation, and $\cactus_{1,r} \cactus_{2,r}$ is
Sch\"utzenberger's promotion.  As an aside, we remark that in this
case the generators $\cactus_{i,i+2}$ encode Assaf's dual equivalence
graph.

More generally, when $C_i$ is the crystal of the $\mu_i$-th exterior
power of the vector representation then the highest weight words of
$C$ are semistandard Young tableaux of weight $\mu$, with at most $n$
columns: the weight of the $i$-th letter specifies the columns in
which the number $i$ appears.  Again, $\cactus_{1,r}$ acts as
evacuation and $\cactus_{1,r} \cactus_{2,r}$ as promotion.  Using
evacuation as a building block, the action of the cactus groups on
semistandard Young tableaux was studied by Chmutov, Glick and
Pylyavskyy~\cite{BK}.

By analogy we call $\ev w = \cactus_{1,r} w$ the evacuation of a
highest weight word $w$, and $\pr w = \cactus_{1,r}\cactus_{2,r} w$
its promotion.  The promotion of $w$ can be obtained as follows:
\begin{itemize}\setlength{\itemsep}{0pt}
\item[] let $w'$ be $w$ without its first letter,
\item[] let $w''$ be the unique highest weight word in the same
  component as $w'$,
\item[] append the uniquely determined letter to $w''$, such that the
  result has the same weight as $w$.
\end{itemize}

This general definition of the promotion operator has been studied in
connection with the cyclic sieving phenomenon.
Rhoades 
established a cyclic sieving phenomenon for
the promotion operator acting on rectangular standard tableaux.  This
was generalised to promotion on invariant words in the crystal of a
minuscule representation by Fontaine and Kamnitzer, 
using the geometric Satake correspondence.  A cyclic sieving
phenomenon for the promotion operator acting on invariant words in
any crystal was given by Westbury~\cite{Westbury2009}, exploiting the
fact that Lusztig's canonical basis for invariant tensors is
preserved by promotion.

Cyclic sieving phenomena for perfect matchings and permutations
together with rotation were established by Rubey and
Westbury~\cite{RubeyWestbury, RubeyWestbury2015}.  There, a basis of
the space of invariant tensors which is invariant under rotation was
constructed, in an elementary way.  The construction involved the two
fundamental theorems of invariant theory, asserting that the tensors
of chord diagrams are a basis of the space of invariant tensors.

The promotion and rotation operators on invariant tensors were shown
to agree by Westbury~\cite{Westbury2009}, in the following sense.  It
is true in general that, given a vector space with a linear operator
of finite order and two bases each preserved by the operator then
there is a bijection between the two bases which intertwines the two
actions of the operator.  In particular, this implies for our setting
that there exists a bijection between chord diagrams and invariant
words which intertwines rotation and promotion.  However constructing
such a bijection explicitly remained an open problem, which we solve
here.

\section{Results}
\begin{figure}
  \begin{center}
  \begin{tikzpicture}[line width=1pt]
    \node (a) [draw=none, minimum size=1.5cm, regular polygon, regular polygon sides=8] at (0,0) {};
    \foreach \n [count=\i from 0, remember=\n as \lastn, evaluate={\i+\lastn}] in {1,2,...,8}
        \node[anchor=(\n-3.5)*(360/8)] at (a.corner \n) {$\n$};
    \draw (a.corner 1) to (a.corner 6);
    \draw (a.corner 2) to (a.corner 4);
    \draw (a.corner 3) to (a.corner 8);
    \draw (a.corner 5) to (a.corner 7);
  \end{tikzpicture}
  \hfil
  \tikzset{->-/.style={decoration={
        markings,
        mark=at position #1 with {\arrow{>}}},postaction={decorate}}}
  \begin{tikzpicture}[line width=1pt]
    \node (a) [draw=none, minimum size=1.5cm, regular polygon, regular polygon sides=5] at (0,0) {};
    \foreach \n [count=\i from 0, remember=\n as \lastn, evaluate={\i+\lastn}] in {1,2,...,5}
        \node[anchor=(\n-2)*(360/5)] at (a.corner \n) {$\n$};
    \draw[->-=.9] (a.corner 1) to (a.corner 5);
    \draw[->-=.9, bend right] (a.corner 2) to (a.corner 4);
    \draw[->-=.9] (a.corner 3) to (a.corner 1);
    \draw[->-=.9, bend right] (a.corner 4) to (a.corner 2);
    \draw[->-=.9] (a.corner 5) to (a.corner 3);
  \end{tikzpicture}
\end{center}
\caption{A $3$-noncrossing perfect matching and a permutation as
    chord diagrams.}
  \label{fig:chord-diagrams}
\end{figure}

We aim at making the action of the cactus group on the highest weight
words of a tensor power of certain representations transparent.  Our
approach works best for tensor products of minuscule representations
of a Lie group.  A representation is \Dfn{minuscule} if the Weyl
group $W$ of the Lie group acts transitively on the weights of the
representation: the set of weights forms a single orbit under the
action of $W$.  The non-trivial minuscule representations are:
\begin{description}\setlength{\itemsep}{0pt}
\item[Type $A_n$:] All exterior powers of the vector representation.
\item[Type $B_n$:] The spin representation.
\item[Type $C_n$:] The vector representation.
\item[Type $D_n$:] The vector representation and the two half-spin
  representations.
\item[Type $E_6$:] The two fundamental representations of dimension
  $27$.
\item[Type $E_7$:] The fundamental representation of dimension $56$.
\end{description}
There are no nontrivial minuscule representations in types $G_2$,
$F_4$ or $E_8$.

For tensor products of exterior powers of the vector representation
of $\GL(n)$, the action of the cactus group is known, as already
mentioned in the introduction.

Highest weight words of weight zero of $\otimes^r S$, where $S$ is
the the spin representation of the spin group $\Spin(2n+1)$ can be
identified directly with fans of $n$ Dyck paths of length $r$.  One
can show that $\ev$ acts on these as reversal.

The vector representation of the odd orthogonal group $\SO(2n+1)$ is
not minuscule, but appears as a direct summand in $S\otimes S$.  In
particular, highest weight words of weight zero of a tensor power of
the vector representation of $\SO(3)$ can be identified with
noncrossing set partitions without singletons, and $\pr$ acts on
these as rotation.

However, our main contributions concern the vector representation of
$\Sp(2n)$ and the adjoint representation of $\GL(n)$ - regarded as
the tensor product of the vector representation and its dual.

\subsection{The vector representation of the symplectic groups}
\label{sec:symplectic-results}
\begin{defn}[Sundaram~\cite{MR2941115}]
  An \Dfn{$n$-symplectic oscillating tableau} of length $r$ and
  (final) shape $\wgt$ is a sequences of partitions
  \[
  \emptyset\!=\!\wgt^0,\wgt^1,\ldots,\wgt^r\!=\!\wgt
  \]
  such that the Ferrers diagrams of two consecutive partitions differ
  by exactly one box, and each partition $\wgt^i$ has at most $n$
  non-zero parts.
\end{defn}

\begin{prop}
  Let $C$ be the crystal corresponding to $\otimes^r V$, where $V$ is
  the vector representation of the symplectic group $\Sp(2n)$.  Then
  the highest weight words of $C$ are obtained from $n$-symplectic
  oscillating tableaux by considering each partition as a vector in
  $\ZZ^n$ and taking successive differences.  Explicitly, the highest
  weight word corresponding to $\osc$ is
  \[
  \wgt^1-\wgt^0,\wgt^2-\wgt^1,\ldots,\wgt^r-\wgt^{r-1}.
  \]
\end{prop}

A now classic bijection due to Sundaram~\cite{MR2941115} maps an
oscillating tableau $\osc$ of length $r$ to a pair
$\big(\M(\osc), \M_T(\osc)\big)$, consisting of a matching of a
subset of $\{1,\dots,r\}$ and a partial standard Young tableau on the
complementary subset.  We describe this bijection in
\cref{sec:growth-diagrams}.
\begin{thm}\label{thm:s1q-partial-matchings}
  Let $\osc$ be an $n$-symplectic oscillating tableau of length $r$,
  not necessarily of empty shape.  Then $\M(\ev\osc)$ is the reversal
  of $\M(\osc)$ and $\M_T(\ev\osc)$ is the Sch\"utzenberger
  evacuation of $\M_T(\osc)$.
\end{thm}

There is a remarkable geometric description of perfect matchings
corresponding to $n$-symplectic oscillating tableaux of empty shape
under Sundaram's bijection: visualise a perfect matching by drawing
its pairs as (straight) diagonals connecting the vertices of a
labelled regular $r$-gon.  Then a perfect matching is
$(n+1)$-noncrossing, and the image of an $n$-symplectic oscillating
tableau, if it contains at most $n$ pairs that mutually cross in this
picture.
\begin{thm}\label{thm:rotation-promotion-matchings}
  The bijection $\M$ between $n$-symplectic oscillating tableaux of
  empty shape and $(n+1)$-noncrossing perfect matchings intertwines
  promotion and rotation, and evacuation and reversal:
  \[
  \rot\M(\osc) = \M(\pr\osc)\text{ and }\rev\M(\osc) = \M(\ev\osc).
  \]
\end{thm}
\subsection{The adjoint representation of the general linear groups}
\label{sec:adjoint-results}
\begin{defn}[Stembridge~\cite{MR899903}]
  A \Dfn{$\GL(n)$-alternating tableau} of length $r$ and weight
  $\wgt$ is a sequence of vectors in $\ZZ^n$
  \[
  \emptyset\!=\!\wgt^0,\wgt^1,\ldots,\wgt^{2r}\!=\!\wgt
  \]
  such that
  \begin{itemize}\setlength{\itemsep}{0pt}
  \item[] the entries in each vector are weakly decreasing,
  \item[] for even $i$, $\wgt^{i+1}$ is obtained from $\wgt^i$ by
    adding $1$ to an entry, and
  \item[] for odd $i$, $\wgt^{i+1}$ is obtained from $\wgt^i$ by
    subtracting $1$ from an entry.
  \end{itemize}
\end{defn}

\begin{prop}
  Let $C$ be the crystal corresponding to $\otimes^r \GL(n)$, where
  $\GL(n)$ is the adjoint representation of the general linear group
  $\GL(n)$.  Then the highest weight words of $C$ are obtained from
  $\GL(n)$-alternating tableaux by taking successive differences.
  Explicitly, the highest weight word corresponding to $\alt$ is the
  sequence of $r$ pairs
  \[
  (\wgt^1-\wgt^0,\wgt^2-\wgt^1),\dots,(\wgt^{2r-1}-\wgt^{2r-2},\wgt^{2r}-\wgt^{2r-1}).
  \]
\end{prop}
It is tempting to regard each vector in an alternating tableau as a
pair of partitions by separating the positive and negative terms.
Indeed, this is what we will do below.  However, for $n>2$ promotion
does not preserve the number of non-zero entries of an alternating
tableau.  In fact, it is not clear whether there is an embedding
$\iota$ of the set of $\GL(n)$-alternating tableaux for into the set
of $\GL(n+1)$-alternating tableaux such that
$\pr\iota(\alt) = \pr\alt$.

In \cref{sec:growth-diagrams}, we introduce a bijection
similar in spirit to Sundaram's, that maps an alternating tableau
$\alt$ of length $r$ to a triple
$\big(\Perm(\alt), \Perm_P(\alt), \Perm_Q(\alt)\big)$, consisting of
a bijection between two subsets, $R$ and $S$, of $\{1,\dots,r\}$, and
two partial standard Young tableaux.  The shapes of these tableaux
are obtained by separating the positive and negative terms in the
weight of the alternating tableaux.  The entries of the first
tableaux then form the complementary subset of $R$, the entries of
the second form the complementary subset of $S$.
\begin{thm}\label{thm:s1q-partial-permutations}
  Let $\alt$ be a $\GL(n)$-alternating tableau of length
  $r\leq \lfloor\frac{n+1}{2}\rfloor$, not necessarily of empty
  weight.  Then $\Perm(\ev\alt)$ is the reversal of the complement of
  $\Perm(\alt)$ and
  \[
  \big(\Perm_P(\ev\alt), \Perm_Q(\ev\alt)\big) =
  \big(\ev\Perm_P(\alt), \ev\Perm_Q(\alt)\big).
  \]
\end{thm}
\begin{thm}\label{thm:rotation-promotion-permutations}
  For $n\geq r-1$ and also for $n\leq 2$ the bijection $\Perm$
  between $\GL(n)$-alternating tableaux of empty weight and
  permutations intertwines rotation and promotion:
  \[
  \rot\Perm(\alt) = \Perm(\pr\alt).
  \]
  For odd $n\geq r$ and for even $n\geq r-1$, it intertwines
  reverse-complement and evacuation:
  \[
  \reco\Perm(\alt) = \Perm(\ev\alt).
  \]
\end{thm}

\section{The cactus groups and local rules}
\label{sec:crystals-local-rules}
\begin{defn}
  The \Dfn{$r$-fruit cactus group}, $\fC_r$, has generators $\cactus_{p,q}$
  for $1\le p<q\le r$ and defining relations
  \begin{itemize}\setlength{\itemsep}{0pt}
  \item $\cactus_{p,q}^2=1$
  \item $\cactus_{p,q}\, \cactus_{k,l}=\cactus_{k,l}\, \cactus_{p,q}$ if $q<k$ or $l<p$
  \item $\cactus_{p,q}\, \cactus_{k,l}=\cactus_{p+q-l,p+q-k}\, \cactus_{p,q}$ if $p\le k<l\le q$
  \end{itemize}
\end{defn}

The following lemma shows that it is sufficient to define the action
of the composite $\cactus_{1,q} \cactus_{2,q}$.  The first relation
was observed by White~\cite[lem.~2.3]{noah}, the second is
essentially how Sch\"utzenberger~\cite[sec.~5]{MR0190017} introduced
evacuation initially.
\begin{lemma}\label{lem:extend-s_1q}
  We have
  \[
    \cactus_{p,q} = \cactus_{1,q}\cactus_{1,q-p+1}\cactus_{1,q}%
    \quad\text{and}\quad%
    \cactus_{1,q} = \cactus_{1,2} \cactus_{2,2}\; \cactus_{1,3} \cactus_{2,3}\; \dots\; \cactus_{1,q} \cactus_{2,q}.
  \]
\end{lemma}
Henriques and Kamnitzer~\cite{MR2219257} defined the action of the
cactus group on $r$-fold tensor products of crystals in terms of
Lusztig's involution introduced in~\cite{MR1182165}.  For
semistandard Young tableaux this involution is precisely
Sch\"utzenberger's evacuation.  However, we follow Lenart's
approach~\cite{MR2361854} and define the action of the cactus group
in terms of van Leeuwen's local rules~\cite[Rule 4.1.1]{MR1661263},
which generalise Fomin's~\cite[A 1.2.7]{MR1676282}.
\begin{defn}\label{def:local-rules}
  Let $\lambda$ be any weight of a Lie group with Weyl group $W$.
  Then $\dom_W(\lambda)$ is the dominant representative of the
  $W$-orbit $W\lambda$.

  Let $A$ be a crystal and $B$ and $C$ be crystals of minuscule
  representations.  Then the \Dfn{local rule}
  \[
  \tau^A_{B,C}\colon A\otimes B\otimes C \rightarrow A\otimes
  C\otimes B
  \]
  is a weight preserving bijection defined for highest weight words
  $\alpha\otimes\beta\otimes\gamma$ as follows: let $\kappa$ be the
  weight of $\alpha$, let $\lambda$ be the weight of
  $\alpha\otimes\beta$ and let $\nu$ be the weight of
  $\alpha\otimes\beta\otimes\gamma$.  Then
  \[
  \tau^A_{B,C}(\alpha\otimes\beta\otimes\gamma)=
  \alpha\otimes\gamma'\otimes\beta',
  \]
  where, regarding $\kappa$, $\lambda$, $\mu$ and $\nu$ as vectors,
  \[
  \mu = \dom_W(\kappa+\nu-\lambda),\quad \gamma' =
  \mu-\kappa\quad\text{and}\quad \beta'=\nu-\mu.
  \]
  We represent this by the following diagram:
  \begin{figure}[H]
  \centering
    \begin{tikzpicture}[scale=1]
      \node (ka) at (0,0) {$\kappa$};
      \node (la) at (0,1) {$\lambda$};
      \node (nu) at (1,1) {$\nu$};
      \node (mu) at (1,0) {$\mu$};
      \draw[->] (ka) -- (la) node [midway, left] {$\beta$};
      \draw[->] (mu) -- (nu) node [midway, right] {$\beta'$};
      \draw[->] (la) -- (nu) node [midway, above] {$\gamma$};
      \draw[->] (ka) -- (mu) node [midway, below] {$\gamma'$};
    \end{tikzpicture}
\caption{}
\label{fig:local}
\end{figure}

  From now on we omit the labels on the edges, because they are
  determined by the weights.

  Any isomorphism between crystals is determined by specifying a
  bijection between the corresponding highest weight words.  Such a
  bijection can then be extended to the whole crystal by applying the
  lowering operators.
\end{defn}

\begin{defn}\label{def:s_1q}
  Let $C_1,\dots,C_r$ be crystals.  Then
  $\cactus_{1,q} \cactus_{2,q}$ is the map
  \[
  \tau_{C_1,C_q}^{C_2\otimes\dots\otimes
    C_{q-1}}\circ\dots\circ\tau_{C_1,C_3}^{C_2}\circ\tau_{C_1, C_2}^I
  \]
  from $C_1\otimes\dots\otimes C_r$ to
  $C_2\otimes\dots\otimes C_q\otimes C_1\otimes
  C_{q+1}\otimes\dots\otimes C_r$.

  Here, to improve readability we omitted identity mappings and wrote
  $\tau^A_{B,C}$ instead of $\tau^A_{B,C}\otimes 1_D$ when applying
  the map to a tensor product $A\otimes B\otimes C\otimes D$.
\end{defn}

A straightforward induction shows that this definition agrees with
Henriques and Kamnitzer's.  Our definition may appear at first sight
less general than theirs, since we require minuscule
representations.  However, it turns out that any crystal can be
embedded in a tensor product of minuscule or so called
quasi-minuscule crystals, for which a local rule is also available.
In fact, for Cartan types other than $E_8$, $F_4$ and $G_2$, tensor
products of minuscule crystals are sufficient.

In particular, promotion and evacuation of $\GL(n)$-alternating
tableaux can be accommodated as follows.  Regard the adjoint
representation as the tensor product $V\otimes V^\ast$, where $V$ is
the vector representation of $\GL(n)$ and $V^\ast$ is its dual.  Both
of these are minuscule.  Thus, we first apply
$\cactus_{1,2r}\cactus_{2,2r}$ to the word interpreted as an element
of $C_1\otimes\dots\otimes C_{2r}$ with $C_1=V, C_2=V^\ast,\dots$
Then we apply $\cactus_{1,2r}\cactus_{2,2r}$ again.  We call the
result of this operation the promotion of the original word.


To illustrate, let us compute the promotion of a $\GL(3)$-alternating
tableau.  The Weyl group of $\GL(n)$ is the symmetric group $\fS_n$,
so $\dom_W$ is just returning its argument sorted in decreasing
order.  The first row is the original alternating tableau.  Regarding
the sequence of successive differences of the vectors in the first
row as an element of $\bigotimes^5(V\otimes V^\ast)$, the second row
is obtained by applying $\cactus_{1,10}\cactus_{2,10}$.  Repeating
this one more time, we obtain the promotion.  For better readability
we write $\bar 1$ in place of $-1$.
\begin{equation}\label{eq:pr-adjoint-example}
\def\arraystretch{1.5}
\begin{array}{ccccccccccccc}
  000&100&10\bar1&20\bar1&2\bar1\bar1&20\bar1&2\bar1\bar1&20\bar1&10\bar1&100&000\\
     &000&00\bar1&10\bar1&1\bar1\bar1&\tikzmark{start}10\bar1&1\bar1\bar1&10\bar1&00\bar1&000&00\bar1&000\\
     &   &000    &100    &10\bar1    &11\bar1                &10\bar1\tikzmark{end}&11\bar1&10\bar1&100&10\bar1&100&000
\end{array}
\begin{tikzpicture}[remember picture,overlay]
  \node[draw,line width=0pt,rectangle,minimum size=1.8cm,fit={(pic cs:start) (pic cs:end)},yshift=3pt] {};
\end{tikzpicture}
\end{equation}
The four vectors in the square demonstrate that the naive embedding
of $\GL(n)$-alternating tableaux into the set of
$\GL(n+1)$-alternating tableaux is not compatible with promotion, as
mentioned in \cref{sec:adjoint-results}: padding the vectors
in the square corresponding to $\kappa$, $\lambda$ and $\nu$ in
\cref{fig:local} with zeros, and applying the local rule, we obtain
the square
\[
\def\arraystretch{1.5}
\begin{array}{cc}
  100\bar1&10\bar1\bar1\\
  110\bar1&11\bar1\bar1,
\end{array}
\]
with $\mu=11\bar1\bar1$, rather than the vector $100\bar1$ one might
expect.

\section{Growth diagram bijections}
\label{sec:growth-diagrams}

In this section we recall Sundaram's bijection (using Roby's
description~\cite{MR2716353}) between oscillating tableaux and
matchings.  We also present a new bijection, in the same spirit,
between alternating tableaux and partial permutations.  In both
cases, the action of the cactus group on highest weight words becomes
particularly transparent when using Fomin's growth diagrams and local
rules for the Robinson-Schensted correspondence.

We give a slightly non-standard presentation with the benefit that
these local rules can be regarded as a variation of the classical
case of \cref{def:local-rules}.

\begin{figure}[h]
  \begin{align*}
  c &=
  \begin{tikzpicture}[baseline={([yshift=-.5ex]current bounding box.center)},scale=2]
    \node (ka) at (0,0) {$\kappa$};
    \node (la) at (0,1) {$\lambda$};
    \node (nu) at (1,1) {$\nu$};
    \node (mu) at (1,0) {$\mu$};
    \draw[<-] (ka) -- (la);
    \draw[<-] (mu) -- (nu);
    \draw[->] (la) -- (nu);
    \draw[->] (ka) -- (mu);
    \node at (0.5,0.5)[rectangle,minimum size=1.5cm,draw] {};
  \end{tikzpicture}
  %
  &\text{\hspace{-2cm}or\hspace{2cm}} c &=
  \begin{tikzpicture}[baseline={([yshift=-.5ex]current bounding box.center)},scale=2]
    \node (ka) at (0,0) {$\lambda$};
    \node (la) at (0,1) {$\lambda$};
    \node (nu) at (1,1) {$\lambda$};
    \node (mu) at (1,0) {$\mu$};
    \draw[<-] (ka) -- (la);
    \draw[<-] (mu) -- (nu);
    \draw[->] (la) -- (nu);
    \draw[->] (ka) -- (mu);
    \node at (0.5,0.5)[rectangle,minimum size=1.5cm,draw] {\huge$\times$};
  \end{tikzpicture}\\
    \mu'&=\dom_{\fS_n}(\kappa'+\nu'-\lambda')
  &
    \mu &= \lambda + \epsilon_1\\
    \lambda'&=\dom_{\fS_n}(\kappa'+\nu'-\mu')
  &
    \lambda &= \mu - \epsilon_1
  \end{align*}
  \caption{Cells of a growth diagram and corresponding local rules.}
  \label{fig:growth-cell}
\end{figure}
In general, a growth diagram is a finite collection of cells (as in
\cref{fig:growth-cell}, where a prime denotes the conjugate
partition), arranged in the form of a Ferrers diagram.  Thus, for
each cell in the diagram all cells above and to the left are also
present.  The four corners of each cell $c$ are labelled with
partitions as indicated.

A difference to \cref{def:local-rules} is that two adjacent
partitions (as for example $\lambda$ and $\kappa$ in
\cref{fig:growth-cell}) either coincide or the one at the head
of the arrow is obtained from the other by adding a single box.  In
the latter case, we write $\lambda\ltd\kappa$ and, if $\kappa$ is
obtained by adding one to the $i$-th part,
$\kappa=\lambda+\epsilon_i$.

The two rules in \cref{fig:growth-cell} determining $\mu$ are
called \Dfn{forward rules}, the two rules in
\cref{fig:growth-cell} determining $\lambda$ are called
\Dfn{backward rules}.

\subsection{Roby's description of Sundaram's correspondence}
\label{sec:Roby}
\begin{figure}
  \begin{center}
\begin{tikzpicture}[scale=0.75]\tiny
% a dotted line to indicate the reflection
\draw[dotted] (1,10) -- (5,6);
%
\foreach \y in {1,...,10}
   \draw (1,\y)--(\y,\y);
\foreach \x in {1,2,...,10}
   \draw (\x,\x)--(\x,10);
% column labels
\foreach \x in {1,2,...,9}
   \draw (\x.5,10.3) node{\footnotesize$\x$};
% row labels
\foreach \x in {1,2,...,9}
   \draw (0.3,\x.4) node{\footnotesize$\x$};
% crosses
\draw (1.5,4.5) node{\huge$\times$};
\draw (2.5,9.5) node{\huge$\times$};
\draw (3.5,6.5) node{\huge$\times$};
% partitions column 0 (from bottom to top)
\draw (.8,.8) node{\footnotesize$\emptyset$};
\foreach \x in {1,2,...,8}
   \draw (.8,\x.8) node{$\emptyset$};
\draw (0.8,9.8) node{\footnotesize$\emptyset$};
% partitions column 1
\draw (1.8,1.8) node{\footnotesize$1$};
\draw (1.8,2.8) node{$1$};
\draw (1.8,3.8) node{$1$};
\foreach \x in {4,5,...,8}
   \draw (1.8,\x.8) node{$\emptyset$};
\draw (1.8,9.8) node{\footnotesize$\emptyset$};
% partitions column 2
\draw (2.8,2.8) node{\footnotesize$11$};
\draw (2.8,3.8) node{$11$};
\foreach \x in {4,5,...,8}
   \draw (2.8,\x.8) node{$1$};
\draw (2.8,9.8) node{\footnotesize$\emptyset$};
% partitions column 3
\draw (3.8,3.8) node{\footnotesize$21$};
\draw (3.8,4.8) node{$2$};
\draw (3.8,5.8) node{$2$};
\draw (3.8,6.8) node{$1$};
\draw (3.8,7.8) node{$1$};
\draw (3.8,8.8) node{$1$};
\draw (3.8,9.8) node{\footnotesize$\emptyset$};
% partitions column 4
\draw (4.8,4.8) node{\footnotesize$2$};
\draw (4.8,5.8) node{$2$};
\draw (4.8,6.8) node{$1$};
\draw (4.8,7.8) node{$1$};
\draw (4.8,8.8) node{$1$};
\draw (4.8,9.8) node{\footnotesize$\emptyset$};
% partitions column 5
\draw (5.8,5.8) node{\footnotesize$21$};
\draw (5.8,6.8) node{$11$};
\draw (5.8,7.8) node{$11$};
\draw (5.8,8.8) node{$11$};
\draw (5.8,9.8) node{\footnotesize$1$};
% partitions column 6
\draw (6.8,6.8) node{\footnotesize$11$};
\draw (6.8,7.8) node{$11$};
\draw (6.8,8.8) node{$11$};
\draw (6.8,9.8) node{\footnotesize$1$};
% partitions column 7
\draw (7.8,7.8) node{\footnotesize$21$};
\draw (7.8,8.8) node{$21$};
\draw (7.8,9.8) node{\footnotesize$2$};
% partitions column 8
\draw (8.8,8.8) node{\footnotesize$211$};
\draw (8.8,9.8) node{\footnotesize$21$};
% partitions column 9
\draw (9.8,9.8) node{\footnotesize$21$};
\end{tikzpicture}
\begin{tikzpicture}[scale=0.75]\tiny
% a dotted line to indicate the reflection
\draw[dotted] (1,10) -- (5,6);
%
\foreach \y in {1,...,10}
   \draw (1,\y)--(\y,\y);
\foreach \x in {1,2,...,10}
   \draw (\x,\x)--(\x,10);
% column labels
\foreach \x in {1,2,...,9}
   \draw (\x.5,10.3) node{\footnotesize$\x$};
% row labels
\foreach \x in {1,2,...,9}
   \draw (0.3,\x.4) node{\footnotesize$\x$};
% crosses
\draw (1.5,8.5) node{\huge$\times$};
\draw (4.5,7.5) node{\huge$\times$};
\draw (6.5,9.5) node{\huge$\times$};
% partitions column 0 (from bottom to top)
\draw (.8,.8) node{\footnotesize$\emptyset$};
\foreach \x in {1,2,...,8}
   \draw (.8,\x.8) node{$\emptyset$};
\draw (0.8,9.8) node{\footnotesize$\emptyset$};
% partitions column 1
\draw (1.8,1.8) node{\footnotesize$1$};
\foreach \x in {2,3,...,7}
   \draw (1.8,\x.8) node{$1$};
\draw (1.8,8.8) node{$\emptyset$};
\draw (1.8,9.8) node{\footnotesize$\emptyset$};
% partitions column 2
\draw (2.8,2.8) node{\footnotesize$11$};
\foreach \x in {3,4,...,7}
   \draw (2.8,\x.8) node{$11$};
\draw (2.8,8.8) node{$1$};
\draw (2.8,9.8) node{\footnotesize$1$};
% partitions column 3
\draw (3.8,3.8) node{\footnotesize$111$};
\foreach \x in {4,5,6,7}
   \draw (3.8,\x.8) node{$111$};
\draw (3.8,8.8) node{$11$};
\draw (3.8,9.8) node{\footnotesize$11$};
% partitions column 4
\draw (4.8,4.8) node{\footnotesize$211$};
\foreach \x in {5,6}
   \draw (4.8,\x.8) node{$211$};
\draw (4.8,7.8) node{$111$};
\draw (4.8,8.8) node{$11$};
\draw (4.8,9.8) node{\footnotesize$11$};
% partitions column 5
\draw (5.8,5.8) node{\footnotesize$221$};
\draw (5.8,6.8) node{$221$};
\draw (5.8,7.8) node{$211$};
\draw (5.8,8.8) node{$21$};
\draw (5.8,9.8) node{\footnotesize$21$};
% partitions column 6
\draw (6.8,6.8) node{\footnotesize$321$};
\draw (6.8,7.8) node{$311$};
\draw (6.8,8.8) node{$31$};
\draw (6.8,9.8) node{\footnotesize$21$};
% partitions column 7
\draw (7.8,7.8) node{\footnotesize$311$};
\draw (7.8,8.8) node{$31$};
\draw (7.8,9.8) node{\footnotesize$21$};
% partitions column 8
\draw (8.8,8.8) node{\footnotesize$31$};
\draw (8.8,9.8) node{\footnotesize$21$};
% partitions column 9
\draw (9.8,9.8) node{\footnotesize$21$};
\end{tikzpicture}
  \end{center}
  \caption{A pair of growth diagrams $\G(\osc)$ and
    $\G(\cactus_{1,9}\osc)$ illustrating
    \cref{thm:s1q-partial-matchings}.  The dotted line
    indicates the axis of reflection for the matchings $\M(\osc)$ and
    $\M(\cactus_{1,9}\osc)$.}
  \label{fig:s1q-partial-matchings}
\end{figure}
\begin{defn}
  Let $\osc=(\wgt_0,\wgt_1,\ldots,\wgt_r)$ be an oscillating
  tableau.  The associated triangular growth diagram $\G(\osc)$
  consists of $r$ left-justified rows, with $i-1$ cells in row $i$
  for $i\in\{1,\dots,r\}$, where row $1$ is the bottom row.  Label
  the cells according to the following specification:
  \begin{itemize}\setlength{\itemsep}{0pt}
  \item[R1] Label the corners of the cells along the diagonal from
    south-west to north-east with the partitions in $\osc$.
  \item[R2] Label the corners of the subdiagonal with the smaller of
    the two partitions labelling the two adjacent corners on the
    diagonal.
  \item[R3] Use the backward rules to determine which cells contain a
    cross.
  \end{itemize}

  Let $\M(\osc)$ be the matching containing a pair $\{i, j\}$ for
  every cross in column $i$ and row $j$ of the $\G(\osc)$.
  Furthermore, let $\M_T(\osc)$ be the partial standard Young tableau
  corresponding to the sequence of partitions along the top border
  of $\G(\osc)$.
\end{defn}
An example for this procedure, which also illustrates
\cref{thm:s1q-partial-matchings}, can be found in
\cref{fig:s1q-partial-matchings}.  Let $w$ be the highest
weight word $1,2,1,-2,2,-1,1,3,-3$.  The partitions in the
corresponding $3$-symplectic oscillating tableau $\osc$ label the
corners of the diagonal of the growth diagram on the left hand side.
Applying the backward rules, we obtain the matching and the partial
standard Young tableau \Yvcentermath1
\[
\M(\osc)=\big\{\{1,4\},\{2,9\},\{3,6\}\big\}\text{ and }
\M_T(\osc)=\young(57,8).
\]
Using \cref{lem:extend-s_1q} and \cref{def:s_1q} one
can compute that $\cactus_{1,9}w$ is the highest weight word
$1, 2, 3, 1, 2, 1, -2, -3, -1$ corresponding to the $3$-symplectic
oscillating tableau labelling the corners of the diagonal of the
growth diagram on the right hand side.  Applying the backward rules
again, we obtain the matching and the partial standard Young tableau
predicted by \cref{thm:s1q-partial-matchings}:
\Yvcentermath1 \Yvcentermath1
\[
\M(\cactus_{1,9}\osc)=\big\{\{1,8\},\{4,7\},\{6,9\}\big\}\text{ and }
\M_T(\cactus_{1,9}\osc)=\young(25,3).
\]

\subsection{A new variant for Stembridge's alternating tableaux}
\label{sec:Stembridge}

\begin{defn}
  Let $\alt=\wgt^0,\wgt^1,\ldots,\wgt^{2r}$ be an alternating
  tableau.  The associated growth diagram $\G(\alt)$ is an
  $r\times r$ square of cells, obtained as follows:
  \begin{itemize}\setlength{\itemsep}{0pt}
  \item[P0] Transform $\alt$ into a sequence of pairs of partitions
    (staircases in Stembridge's terminology)
    \[
    (\wgtAp^0,\wgtAn^0),(\wgtAp^1,\wgtAn^1),\dots,(\wgtAp^{2r},\wgtAn^{2r}).
    \]
    Each vector $\wgt^i$ is a weakly decreasing sequence of integers.
    We obtain the positive part of the staircase, the partition
    $\wgtAp^i$ from $\wgt^i$ by removing all entries less than or
    equal to zero.  The negative part of the staircase, $\wgtAn^i$ is
    obtained from $\wgt^i$ by removing all entries greater than or
    equal to zero, reversing the signs of the remaining entries and
    reversing the sequence.
  \item[P1] Label the corners of the cells along the diagonal from
    north-west to south-east with these staircases.
  \item[P2] Apply the backward rules (rotated counterclockwise by
    $90\degree$) on the positive parts of the staircases to determine
    which cells below the diagonal contain a cross.
  \item[P3] Use the backward rules (rotated clockwise by $90\degree$)
    on the negative parts of the staircases to determine which cells
    above the diagonal contain a cross.
  \end{itemize}

  Let $\Perm(\alt)$ be the partial permutation mapping $i$ to $j$ for
  every cross in column $i$ and row $j$ of $\G(\alt)$, and let
  $\big(\Perm_P(\alt), \Perm_Q(\alt)\big)$ be the pair of partial
  standard Young tableau corresponding to the sequence of partitions
  along the bottom and the right border of $\G(\alt)$, respectively.
\end{defn}


An example for this procedure, which also illustrates
\cref{thm:s1q-partial-permutations}, can be found in
\cref{fig:s1q-partial-permutations}.  Let $w$ be the $\GL(10)$
highest weight word
\[
(e_1, -e_{10}), (e_1, -e_{10}), (e_{10}, -e_9), (e_9, -e_{10}),
(e_{10}, -e_{10}), (e_2, -e_{10}),
\]
where $e_i$ is the $i$-th standard vector.  The staircases in the
corresponding alternating tableau $\alt$ label the corners of the
diagonal of the growth diagram on the left hand side, where we write
the negative partitions with bars.  Applying the backward rules, we
obtain the partial permutation and the partial standard Young
tableaux \Yvcentermath1
\[
\Perm(\alt)=\big\{(3,2),(4,1),(5,4)\big\},
\Perm_P(\alt)=\young(356),\text{ and } \Perm_Q(\alt)=\young(12,6).
\]
On the right hand side of the figure the growth diagram obtained by
applying the same procedure to $\cactus_{1,6}w$, which yields
\Yvcentermath1 \Yvcentermath1
\[
\Perm(\alt)=\big\{(2,3),(3,6),(4,5)\big\},
\Perm_P(\alt)=\young(124),\text{ and } \Perm_Q(\alt)=\young(16,5).
\]
as predicted by \cref{thm:s1q-partial-permutations}.

Finally, consider the $\GL(3)$-alternating tableau in the first row
of~\eqref{eq:pr-adjoint-example}, which corresponds to the
permutation depicted in \cref{fig:chord-diagrams}.  However,
its promotion, as computed in the last row of~\eqref{eq:pr-adjoint-example}, is different from the
alternating tableau corresponding to the rotated permutation.
Indeed, the hypothesis of
\cref{thm:rotation-promotion-permutations} is not satisfied.


\begin{figure}
  \begin{center}
\begin{tikzpicture}[scale=0.9]\tiny
% thick diagonal
\draw[line width=1.5pt] (7,1) -- (7,2) -- (6,2) -- (6,3) -- (5,3) -- (5,4) --
(4,4) -- (4,5) -- (3,5) -- (3,6) -- (2,6) -- (2,7) -- (1,7);
\foreach \y in {1,...,7}
   \draw (1,\y)--(7,\y);
\foreach \x in {1,2,...,7}
   \draw (\x,1)--(\x,7);
% column labels
\foreach \x in {1,2,...,6}
   \draw (\x.5,7.3) node{\footnotesize$\x$};
% row labels
\foreach \x in {1,2,...,6}
   \draw (0.3,7.4-\x) node{\footnotesize$\x$};
% crosses
\draw (3.5,5.5) node{\huge$\times$};
\draw (4.5,6.5) node{\huge$\times$};
\draw (5.5,3.5) node{\huge$\times$};
% partitions column 0 (from bottom to top)
\draw (.8,.7) node{\footnotesize$\emptyset$};
\foreach \x in {1,2,...,5}
   \draw (.8,\x.8) node{$\emptyset$};
\draw (0.8,6.7) node{\footnotesize$\emptyset$};
% partitions column 1
\draw (1.8,0.7) node{\footnotesize$1$};
\foreach \x in {1,2,...,4}
   \draw (1.8,\x.8) node{$1$};
\draw (1.8,5.7) node{\footnotesize$1\bar1$};
\draw (1.8,6.7) node{\footnotesize$1$};
% partitions column 2
\draw (2.8,0.7) node{\footnotesize$2$};
\foreach \x in {1,2,...,3}
   \draw (2.8,\x.8) node{$2$};
\draw (2.8,4.7) node{\footnotesize$2\bar2$};
\draw (2.8,5.7) node{\footnotesize$2\bar1$};
\draw (2.8,6.8) node{$\bar\emptyset$};
% partitions column 3
\draw (3.8,0.7) node{\footnotesize$2$};
\foreach \x in {1,2}
   \draw (3.8,\x.8) node{$2$};
\draw (3.7,3.7) node{\footnotesize$2\bar1\bar1$};
\draw (3.8,4.7) node{\footnotesize$2\bar1$};
\draw (3.8,5.8) node{$\bar 1$};
\draw (3.8,6.8) node{$\bar\emptyset$};
% partitions column 4
\draw (4.8,0.7) node{\footnotesize$2$};
\draw (4.8,1.8) node{$2$};
\draw (4.8,2.7) node{\footnotesize$2\bar2$};
\draw (4.8,3.7) node{\footnotesize$2\bar1$};
\foreach \x in {4,5,6}
   \draw (4.8,\x.8) node{$\bar\emptyset$};
% partitions column 5
\draw (5.8,0.7) node{\footnotesize$2$};
\draw (5.8,1.7) node{\footnotesize$2\bar2$};
\draw (5.8,2.7) node{\footnotesize$2\bar1$};
\draw (5.8,3.8) node{$\bar1$};
\foreach \x in {4,5,6}
   \draw (5.8,\x.8) node{$\bar\emptyset$};
% partitions column 6
\draw (6.7,0.7) node{\footnotesize$21\bar3$};
\draw (6.7,1.7) node{\footnotesize$21\bar2$};
\draw (6.8,2.7) node{\footnotesize$\bar1$};
\draw (6.8,3.7) node{\footnotesize$\bar1$};
\draw (6.8,4.7) node{\footnotesize$\bar\emptyset$};
\draw (6.8,5.7) node{\footnotesize$\bar\emptyset$};
\draw (6.8,6.7) node{\footnotesize$\bar\emptyset$};
\end{tikzpicture}
\hfil
\begin{tikzpicture}[scale=0.9]\tiny
\draw[line width=1.5pt] (7,1) -- (7,2) -- (6,2) -- (6,3) -- (5,3) -- (5,4) --
(4,4) -- (4,5) -- (3,5) -- (3,6) -- (2,6) -- (2,7) -- (1,7);
\foreach \y in {1,...,7}
   \draw (1,\y)--(7,\y);
\foreach \x in {1,2,...,7}
   \draw (\x,1)--(\x,7);
% column labels
\foreach \x in {1,2,...,6}
   \draw (\x.5,7.3) node{\footnotesize$\x$};
% row labels
\foreach \x in {1,2,...,6}
   \draw (0.3,7.4-\x) node{\footnotesize$\x$};
% crosses
\draw (2.5,4.5) node{\huge$\times$};
\draw (3.5,1.5) node{\huge$\times$};
\draw (4.5,2.5) node{\huge$\times$};
% partitions column 0 (from bottom to top)
\draw (.8,.7) node{\footnotesize$\emptyset$};
\foreach \x in {1,2,...,5}
   \draw (.8,\x.8) node{$\emptyset$};
\draw (0.8,6.7) node{\footnotesize$\emptyset$};
% partitions column 1
\draw (1.8,0.7) node{\footnotesize$1$};
\foreach \x in {1,2,...,4}
   \draw (1.8,\x.8) node{$1$};
\draw (1.8,5.7) node{\footnotesize$1\bar1$};
\draw (1.8,6.7) node{\footnotesize$1$};
% partitions column 2
\draw (2.8,0.7) node{\footnotesize$1$};
\foreach \x in {1,2,3}
   \draw (2.8,\x.8) node{$1$};
\draw (2.8,4.7) node{\footnotesize$2\bar2$};
\draw (2.8,5.7) node{\footnotesize$2\bar1$};
\draw (2.8,6.8) node{$\bar\emptyset$};
% partitions column 3
\draw (3.8,0.7) node{\footnotesize$1$};
\foreach \x in {1,2}
   \draw (3.8,\x.8) node{$2$};
\draw (3.7,3.7) node{\footnotesize$2\bar2$};
\draw (3.8,4.7) node{\footnotesize$21\bar1$};
\draw (3.8,5.8) node{$\bar 1$};
\draw (3.8,6.8) node{$\bar\emptyset$};
% partitions column 4
\draw (4.8,0.7) node{\footnotesize$1$};
\draw (4.8,1.8) node{$2$};
\draw (4.8,2.7) node{\footnotesize$3\bar3$};
\draw (4.8,3.7) node{\footnotesize$3\bar2$};
\draw (4.8,4.8) node{$\bar2$};
\draw (4.8,5.8) node{$\bar1$};
\draw (4.8,6.8) node{$\bar\emptyset$};
% partitions column 5
\draw (5.8,0.7) node{\footnotesize$11$};
\draw (5.7,1.7) node{\footnotesize$21\bar3$};
\draw (5.7,2.7) node{\footnotesize$31\bar3$};
\draw (5.8,3.8) node{$\bar2$};
\draw (5.8,4.8) node{$\bar2$};
\draw (5.8,5.8) node{$\bar1$};
\draw (5.8,6.8) node{$\bar\emptyset$};
% partitions column 6
\draw (6.7,0.7) node{\footnotesize$21\bar3$};
\draw (6.7,1.7) node{\footnotesize$22\bar3$};
\draw (6.8,2.7) node{\footnotesize$\bar3$};
\draw (6.8,3.7) node{\footnotesize$\bar2$};
\draw (6.8,4.7) node{\footnotesize$\bar2$};
\draw (6.8,5.7) node{\footnotesize$\bar1$};
\draw (6.8,6.7) node{\footnotesize$\bar\emptyset$};
\end{tikzpicture}
  \end{center}
  \caption{A pair of growth diagrams $\G(\alt)$ and
    $\G(\cactus_{1,6}\alt)$ illustrating
    \cref{thm:s1q-partial-permutations}.}
  \label{fig:s1q-partial-permutations}
\end{figure}

\begingroup\emergencystretch=3em
\printbibliography
\endgroup

\end{document}
